public class HashTableImpl implements HashTable{
	private class ListItem{
		public String key;
		public String value;
		public ListItem next;
		
		public ListItem(String key, String value, ListItem next){
			this.key = key;
			this.value = value;
			this.next = next;
		}
	} // List item containing key and the associated object 
	
	private int count; // Number of elements in the Hash Table
	
	private static final int SIZE = 1000; //max size of the Hash Table
	private static final int C1 = 557; // first constant for hash function
	private static final int C2 = 811; // second constant for hash function
	
	private ListItem[] Table; // Hash Table
	
	private static int Hash(String s){
		int sum = 0;
		for (int i = 0; i < s.length(); i++){
			sum += s.charAt(i) + i;
		}
		return (C1 * sum + C2) % SIZE;
	}
	
	public HashTableImpl(){
		Table = new ListItem[SIZE];
		count = 0;
	}
	public boolean isEmpty(){
		if (count == 0){
			return true;
		}
		else{
			return false;
		}
	}
	
	public int size(){
		return count;
	}
	public void put(String key, String value){
		if (key == null){
			throw  new NullPointerException("Null-key unacceptable!!!");
		}
		int index = Hash(key);
		ListItem item = Table[index];
		while (item != null && !key.equals(item.key)){
			item = item.next;
		}
		if (item == null){ // such a key is not in the Hash Table
			ListItem newItem = new ListItem(key, value, Table[index]);
			Table[index] = newItem;
			count++;
		} 
		else{
			item.value = value;
		}
	}
	public String get(String key){
		if (key == null){
			throw  new NullPointerException("Null-key unacceptable!!!");
		}
		int index = Hash(key);
		ListItem item = Table[index];
		while(item != null && !key.equals(item.key)){
			item = item.next;
		}
		if (item == null){ // such a key is not in the Hash Table
			return null;
		}
		return item.value;
	}
	public String remove(String key){
		if (key == null){
			throw  new NullPointerException("Null-key unacceptable!!!");
		}
		int index = Hash(key);
		ListItem prev = null; 
		ListItem item = Table[index];
		while(item != null && !key.equals(item.key)){
			prev = item;
			item = item.next;
		}
		if (item == null){ // such a key is not in the Hash Table
			return null;
		}
		if (prev == null){
			Table[index] = item.next;
			count--;
		}
		else{
			prev.next = item.next;
			count--;
		}
		return item.value;
	}
	public void clear(){
		for (int i = 0; i < SIZE; i++)
		{
			Table[i] = null;
		}
		count = 0;
	}
}